'''
https://leetcode.cn/problems/merge-k-sorted-lists/
'''
from typing import List, Optional

from c03_list.utils import ListNode


class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        # 使用归并思想
        def process(l, r) -> ListNode:
            if l == r: return lists[l]
            m = (l + r) // 2
            l1 = process(l, m)
            l2 = process(m + 1, r)
            return merge(l1, l2)
        def merge(l1, l2) -> ListNode:
            watch_dog = ListNode()
            cur = watch_dog
            while l1 and l2:
                if l1.val < l2.val:
                    cur.next = l1
                    l1 = l1.next
                else:
                    cur.next = l2
                    l2 = l2.next
                cur = cur.next
            cur.next = l1 if l1 else l2
            return watch_dog.next
        return process(0, len(lists) - 1) if lists else None